#ifndef CORE_H
# include "..\..\..\inc\System\Core.h"
#endif
#include "BitArray.hpp"
#include <string.h>
using namespace Structs;

namespace Structs { namespace Collections {

	BitArray::BitArray(uint size)
    {
        _size = size;
    }

    void BitArray::Destroy(BitArray &p)
    {
        if (&p == nullptr)
            return;
        if (p._divisor != 0)
            for (uint i = 0; i < BITVEC_NPTR; i++)
                Destroy(*p.u.Sub[i]);
    }

    uint BitArray::getLength() { return _size; }

	bool BitArray::Get(uint index)
        {
            if (index == 0 || index > _size)
                return false;
            index--;
            BitArray* p = this;
            while (p->_divisor != 0)
            {
                uint bin = index / p->_divisor;
                index %= p->_divisor;
                p = p->u.Sub[bin];
                if (p == nullptr) return false;
            }
            if (p->_size <= BITVEC_NBIT)
                return ((p->u.Bitmap[index / BITVEC_SZELEM] & (1 << (int)(index & (BITVEC_SZELEM - 1)))) != 0);
            uint h = BITVEC_HASH(index++);
            while (p->u.Hash[h] != 0)
            {
                if (p->u.Hash[h] == index) return true;
                h = (h + 1) % BITVEC_NINT;
            }
            return false;
        }

		RC BitArray::Set(uint index)
        {
            Debug_Assert(index > 0);
            Debug_Assert(index <= _size);
            index--;
            BitArray *p = this;
            while (p->_size > BITVEC_NBIT && p->_divisor != 0)
            {
                uint bin = index / p->_divisor;
                index %= p->_divisor;
                if (p->u.Sub[bin] == nullptr)
                    p->u.Sub[bin] = new BitArray(p->_divisor);
                p = p->u.Sub[bin];
            }
            if (p->_size <= BITVEC_NBIT)
            {
                p->u.Bitmap[index / BITVEC_SZELEM] |= (byte)(1 << (int)(index & (BITVEC_SZELEM - 1)));
                return RC::OK;
            }
            uint h = BITVEC_HASH(index++);
            // if there wasn't a hash collision, and this doesn't completely fill the hash, then just add it without worring about sub-dividing and re-hashing.
            if (p->u.Hash[h] == 0)
                if (p->_set < (BITVEC_NINT - 1))
                    goto bitvec_set_end;
                else
                    goto bitvec_set_rehash;
            // there was a collision, check to see if it's already in hash, if not, try to find a spot for it 
            do
            {
                if (p->u.Hash[h] == index) return RC::OK;
                h++;
                if (h >= BITVEC_NINT) h = 0;
            } while (p->u.Hash[h] != 0);
        // we didn't find it in the hash.  h points to the first available free spot. check to see if this is going to make our hash too "full".
        bitvec_set_rehash:
            if (p->_set >= BITVEC_MXHASH)
            {
                uint* values = new uint[BITVEC_NINT];
                memcpy(values, p->u.Hash, sizeof(p->u.Hash));
                memset(p->u.Sub, 0, sizeof(p->u.Sub));
                p->_divisor = (uint)((p->_size + BITVEC_NPTR - 1) / BITVEC_NPTR);
                RC rc = p->Set(index);
                for (uint j = 0; j < BITVEC_NINT; j++)
                    if (values[j] != 0) rc |= p->Set(values[j]);
                return rc;
            }
        bitvec_set_end:
            p->_set++;
            p->u.Hash[h] = index;
            return RC::OK;
        }

		void BitArray::Clear(uint index, uint buffer[])
        {
            Debug_Assert(index > 0);
            index--;
            BitArray* p = this;
            while (p->_divisor != 0)
            {
                uint bin = index / p->_divisor;
                index %= p->_divisor;
                p = p->u.Sub[bin];
                if (p == nullptr) return;
            }
            if (p->_size <= BITVEC_NBIT)
                p->u.Bitmap[index / BITVEC_SZELEM] &= (byte)~((1 << (int)(index & (BITVEC_SZELEM - 1))));
            else
            {
                uint* values = buffer;
                memcpy(values, p->u.Hash, sizeof(p->u.Hash));
                memset(p->u.Hash, 0, sizeof(p->u.Hash));
                p->_set = 0;
                for (uint j = 0; j < BITVEC_NINT; j++)
                    if (values[j] != 0 && values[j] != (index + 1))
                    {
                        uint h = BITVEC_HASH(values[j] - 1);
                        p->_set++;
                        while (p->u.Hash[h] != 0)
                        {
                            h++;
                            if (h >= BITVEC_NINT) h = 0;
                        }
                        p->u.Hash[h] = values[j];
                    }
            }
		}
}}